// https://www.lintcode.com/problem/k-sum/description

class Solution {
public:
    /**
     * @param A: An integer array
     * @param k: A positive integer (k <= length(A))
     * @param target: An integer
     * @return: An integera
     */
    // int kSum(vector<int> &A, int k, int target) {
    //     int n = A.size();
    //     vector<vector<int>> res(k + 1, vector<int>(target + 1, 0));
    //     for (int i = 0; i < target + 1; ++i)
    //     {
    //         res[0][i] = 0;
    //     }
    //     for (int i = 0; i < k + 1; ++i)
    //     {
    //         res[i][0] = 0;
    //     }
    //     for (int t = 0; t < n; ++t)
    //     {
    //         for (int i = 1; i < k + 1; ++i)
    //         {
    //             for (int j = A[t]; j < target + 1; ++j)
    //             {
    //                 res[i][j] += res[i - 1][j - A[t]];
    //             }
    //         }
    //     }
    //     return res[k][target];
    // }
    
    // 法一：
    // 要知道还有几个数可选，以及它们的和需要是多少:序列加状态
    // • 状态:f[i][k][s]表示有多少种方法可以在前i个数中选出k个，使得它们 的和是s
    // int kSum(vector<int> &A, int k, int target) {
    //     int n = A.size();
    //     vector<vector<vector<int>>> res(n + 1, vector<vector<int>>(k + 1, vector<int>(target + 1)));
    //     for (int j = 0; j < k + 1; ++j)
    //     {
    //         for (int t = 0; t < target + 1; ++t)
    //         {
    //             res[0][j][t] = 0;
    //         }
    //     }
    //     res[0][0][0] = 1; //重要，不然后面都是0了！！！ res[n][m][0]都是1
    //     for (int i = 1; i < n + 1; ++i)
    //     {
    //         for (int j = 0; j < k + 1; ++j)
    //         {
    //             for (int t = 0; t < target + 1; ++t)
    //             {
    //                 res[i][j][t] = res[i - 1][j][t];
    //                 // if (j > 0 && t - A[i] >= 0)
    //                     // res[i][j][t] += res[i - 1][j - 1][t - A[i]];
    //                 if (j > 0 && t - A[i - 1] >= 0)
    //                     res[i][j][t] += res[i - 1][j - 1][t - A[i - 1]];
    //             }
    //         }
    //     }
    //     return res[n][k][target];
    // }
    
    // 法二：滚动数组
    int kSum(vector<int> &A, int k, int target) {
        int n = A.size();
        vector<vector<vector<int>>> res(2, vector<vector<int>>(k + 1, vector<int>(target + 1)));
        int old = 0;
        int now = 0;
        for (int j = 0; j < k + 1; ++j)
        {
            for (int t = 0; t < target + 1; ++t)
            {
                res[now][j][t] = 0;
            }
        }
        res[now][0][0] = 1; //重要，不然后面都是0了！！！ res[n][m][0]都是1
        for (int i = 1; i < n + 1; ++i)
        {
            old = now;
            now = 1 - now;
            for (int j = 0; j < k + 1; ++j)
            {
                for (int t = 0; t < target + 1; ++t)
                {
                    res[now][j][t] = res[old][j][t];
                    // if (j > 0 && t - A[i] >= 0)
                        // res[i][j][t] += res[i - 1][j - 1][t - A[i]];
                    if (j > 0 && t - A[i - 1] >= 0)
                        res[now][j][t] += res[old][j - 1][t - A[i - 1]];
                }
            }
        }
        return res[now][k][target];
    }
};